//
// Created by xili on 2024/8/24 16:14.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class Solution {
public:
    long long minimumTime(vector<int> &time, int totalTrips) {
        int minV = *min_element(time.begin(), time.end());
        long long left = 1;
        long long right = (long long) totalTrips * minV;
        long long ans = right;
        while (left <= right) {
            long long mid = left + (right - left) / 2;
            if (ok(time, totalTrips, mid)) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    bool ok(vector<int> &time, int total, long long cur) {
        long long sum = 0;
        for (auto &item: time) {
            sum += cur / item;
            if (sum >= total) {
                return true;
            }
        }
        return sum >= total;
    }
};
